package 拓扑排序;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class course2 {
    public boolean canFinish(int numCourses,int[][] prerequisites){
//        存储每个节点的入度
        int[] indegrees=new int[numCourses];
        List<List<Integer>> adjanency=new ArrayList<>();
        Queue<Integer> queue=new LinkedList<>();
        for (int i=0;i<numCourses;++i){
            adjanency.add(new ArrayList<>());
        }
        for (int[] course:prerequisites){
//            course[0]依赖course[1]，那么course[0]的入度就+1
            indegrees[course[0]]++;
            adjanency.get(course[1]).add(course[0]);
        }
//        将入度为0的节点加入队列
        for (int i=0;i<numCourses;++i){
            if(indegrees[i]==0) queue.add(i);
        }
        while (!queue.isEmpty()){
            int pre=queue.poll();
            numCourses--;
//            获取邻接顶点
            for (int next:adjanency.get(pre)){
//                如果邻接顶点入度变为0，那么就加入队列
                if(--indegrees[next]==0) queue.add(next);
            }
        }
//        如果numCourse不为0，那么说明在拓扑排序过程中，存在入度不为0的顶点，说明存在环
        return numCourses==0;
    }
}
